﻿#ifndef __SS_KMP_H__
#define __SS_KMP_H__

namespace StarSeeker
{
	template<typename T>
	inline void MakeNext(const T* key, short* next, int keyLen)
	{
		int q, k;
		next[0] = 0;
		for (q = 1, k = 0; q < keyLen; ++q)
		{
			while (k > 0 && key[q] != key[k])
				k = next[k - 1];
			if (key[q] == key[k])
			{
				k++;
			}
			next[q] = k;
		}
	}

	template<typename T>
	inline int KMP(const T* str, int strLen, const T* key, int keyLen, short* next)
	{
		int i, q;
		for (i = 0, q = 0; i < strLen; ++i)
		{
			while (q > 0 && key[q] != str[i])
				q = next[q - 1];
			if (key[q] == str[i])
			{
				q++;
			}
			if (q == keyLen)
			{
				return i - keyLen + 1;
			}
		}
		return -1;
	}

	template<typename T>
	inline int StringMatchingByKmp(const T* str, int strLen, const T* key, int keyLen)
	{
		int ret = -1;
		if (strLen>0 && keyLen>0 && strLen<1024*1024 && keyLen<1024)
		{
			short* next = new short[keyLen+1];
			memset(next, 0, (keyLen + 1)*sizeof(short));
			MakeNext(key, next, keyLen);
			ret = KMP(str, strLen, key, keyLen, next);
			delete[] next;
		}
		return ret;
	}
	template<typename T>
	inline unsigned int StringSearching(const T* str, unsigned int strLen, const T* key, unsigned int keyLen)
	{
		int ret = StringMatchingByKmp(str, (int)strLen, key, (int)keyLen);
		if (ret >= 0)
		{
			return (unsigned int)ret;
		}
		return 0xffffffff;
	}
}
#endif
